package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.Unknown;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * https://leetcode.com/problems/binary-watch/
 * Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.
 */
public class LC401  implements Unknown {
    final int[] leds = new int[]{1, 2, 4, 8, 1, 2, 4, 8, 16, 32};
    final int hour = 4;// <4是小时位
    List<String> result = new ArrayList<>();

    public List<String> readBinaryWatch(int num) {
        backtracing(num, 0, 0, 0);
        return result;
    }

    public void backtracing(int todo, int hour, int minute, int startIndex) {
        if (todo == 0) {
            if (hour <= 11 && minute <= 59) {
                result.add(hour + ":" + String.format("%02d", minute));
            }
        } else if (leds.length - startIndex == todo) {//直接fill结果
            for (int i = startIndex; i < leds.length; i++) {
                if (i < 4) {
                    hour += leds[i];
                } else {
                    minute += leds[i];
                }
            }
            if (hour <= 11 && minute <= 59) {
                result.add(hour + ":" + String.format("%02d", minute));
            }
        } else {
            //off
            backtracing(todo, hour, minute, startIndex + 1);
            //on
            if (startIndex < 4) {
                hour += leds[startIndex];
            } else {
                minute += leds[startIndex];
            }
            backtracing(todo - 1, hour, minute, startIndex + 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(new LC401().readBinaryWatch(0));
        System.out.println(new LC401().readBinaryWatch(1).size());
        System.out.println(new LC401().readBinaryWatch(2).size());

        String[] a = {"0:48", "0:40", "0:24", "0:36", "0:20", "0:12", "0:34", "0:18", "0:10", "0:06", "0:33", "0:17", "0:09", "0:05", "0:03", "8:32", "8:16", "8:08", "8:04", "8:02", "8:01", "4:32", "4:16", "4:08", "4:04", "4:02", "4:01", "12:00", "2:32", "2:16", "2:08", "2:04", "2:02", "2:01", "10:00", "6:00", "1:32", "1:16", "1:08", "1:04", "1:02", "1:01", "9:00", "5:00", "3:00"};
        String[] b = {"0:03", "0:05", "0:06", "0:09", "0:10", "0:12", "0:17", "0:18", "0:20", "0:24", "0:33", "0:34", "0:36", "0:40", "0:48", "1:01", "1:02", "1:04", "1:08", "1:16", "1:32", "2:01", "2:02", "2:04", "2:08", "2:16", "2:32", "3:00", "4:01", "4:02", "4:04", "4:08", "4:16", "4:32", "5:00", "6:00", "8:01", "8:02", "8:04", "8:08", "8:16", "8:32", "9:00", "10:00"};

        System.out.println(Arrays.stream(a).sorted().collect(Collectors.toList()));
        System.out.println(Arrays.stream(b).sorted().collect(Collectors.toList()));
    }
}
